package test.algorithm.FastSlowPointer;

/**
 * 堆排序
 * @author serenity
 *
 */
public class HeapSort {
	
	
	/**
	 * 元素交换
	 * @param k
	 * @param i
	 * @param j
	 */
	public static void swap(int k[], int i, int j)
	{
		int temp;
	
		temp = k[i];
		k[i] = k[j];
		k[j] = temp;
	}
	
	/**
	 * 调整堆 
	 * @param k 序列
	 * @param s 父节点下标
	 * @param n 堆的元素个数
	 */
	public static void HeapAdjust(int k[], int s , int n)
	{
		// 最大节点下标
		int largest;
		// 左孩子下标
		int l;
		// 右孩子
		int r;

		for( l=leftChild(s); l < n; l=leftChild(s) )
		{
			//先默认设置父节点下标给largest
			largest = s;
			 
			// 如果左孩子大于父亲，largest指向左孩子
			if( l < n &&  k[largest] < k[l] )
			{
				largest = l;
			}
			
			r = rightChild(s);
			
			//右孩子大于largest，largest指向右孩子
			if( r < n &&  k[largest] < k[r] ){
				largest = r;
			}
			
			//如果largest指向父亲，则已是大顶堆，跳出循环
			if( largest==s )
			{
				break;
			}
			
			//父节点和largest互换
			swap(k,s,largest);
			//移动后的节点赋给父节点循环
			s = largest;
		}

	}
	
	public static void HeapSort(int k[]){
		int i;
		
		//创建大顶堆，从最后一个节点的父节点开始
		for( i=(k.length-1)/2; i >= 0; i-- )
		{	
			HeapAdjust(k, i ,k.length);
		}

		for( i=k.length-1; i >= 0; i-- )
		{
			//第0个元素与第i个元素互换
			swap(k, 0, i);
			//重新调整堆，i为堆大小
			HeapAdjust(k, 0 ,i);
		}
	}
	
	
	
	/**
	 * 获取左孩子下标
	 * @param i
	 * @return
	 */
	private static int leftChild(int i){
		return 2*i+1;
	}
	
	/**
	 * 获取右孩子下标
	 * @param i
	 * @return
	 */
	private static int rightChild(int i){
		return 2*i+2;
	}
	
	/**
	 * 获取父节点下标
	 * @param i
	 * @return
	 */
	private static int Parent(int i)
	{
	    return (i-1)/2;
	}
	
	public static void main(String args[] ){
		//int[] a = { 5, 2,3,6,4,8,7,1,9};
		//int[] a = {-1, 5, 2, 6, 0, 3, 9, 1, 7, 4};
		int[] a = {16, 14, 10, 8, 7, 9, 3, 2, 4, 1};

		HeapSort(a);
		
		for(int i : a){
			System.out.print(i+" ");
		}
	}

}
